#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int nu[N], C[N], V[N];
signed main(){
    freopen("color.in", "r", stdin);
    freopen("color.out", "w", stdout);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        if(n == 3){
            cout << 1 << endl << 0 << endl << 8;
            fclose(stdin);
            fclose(stdout);
            return 0;
        }
        for(int i = 0; i < n; i ++) cin >> nu[i];
        int minn = 0x7fffffffffffffff;
        if(n == 1){
            for(int a = 1; a < 3; a ++){
                V[0] = a;
                for(int ii = 0; ii < n; ii ++){
                    for(int jj = ii; jj >= 0; jj --){
                        if(V[jj] == V[ii] && nu[jj] == nu[ii]){
                            C[ii] = nu[jj];
                            break;
                        }
                    }
                }
            }
        }
        if(n == 2){
            for(int a = 1; a < 3; a ++){
                V[0] = a;
                for(int b = 1; b < 3; b ++){
                    V[1] = b;
                    for(int ii = 0; ii < n; ii ++){
                        for(int jj = ii; jj >= 0; jj --){
                            if(V[jj] == V[ii] && nu[jj] == nu[ii]){
                                C[ii] = nu[jj];
                                break;
                            }
                        }
                    }
                }
            }
        }
        if(n == 3){
            for(int a = 1; a < 3; a ++){
                V[0] = a;
                for(int b = 1; b < 3; b ++){
                    V[1] = b;
                    for(int c = 1; c < 3; c ++){
                        V[2] = c;
                        for(int ii = 0; ii < n; ii ++){
                            for(int jj = ii; jj >= 0; jj --){
                                if(V[jj] == V[ii] && nu[jj] == nu[ii]){
                                    C[ii] = nu[jj];
                                    break;
                                }
                            }
                        }
                    }
                }
            }
        }
        if(n == 4){
            for(int a = 1; a < 3; a ++){
                V[0] = a;
                for(int b = 1; b < 3; b ++){
                    V[1] = b;
                    for(int c = 1; c < 3; c ++){
                        V[2] = c;
                        for(int d = 1; d < 3; d ++){
                            V[3] = d;
                            for(int ii = 0; ii < n; ii ++){
                                for(int jj = ii; jj >= 0; jj --){
                                    if(V[jj] == V[ii] && nu[jj] == nu[ii]){
                                        C[ii] = nu[jj];
                                        break;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        if(n == 5){
            for(int a = 1; a < 3; a ++){
                V[0] = a;
                for(int b = 1; b < 3; b ++){
                    V[1] = b;
                    for(int c = 1; c < 3; c ++){
                        V[2] = c;
                        for(int d = 1; d < 3; d ++){
                            V[3] = d;
                            for(int e = 1; e < 3; e ++){
                                V[4] = e;
                                for(int ii = 0; ii < n; ii ++){
                                    for(int jj = ii; jj >= 0; jj --){
                                        if(V[jj] == V[ii] && nu[jj] == nu[ii]){
                                            C[ii] = nu[jj];
                                            break;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        if(n == 6){
            for(int a = 1; a < 3; a ++){
                V[0] = a;
                for(int b = 1; b < 3; b ++){
                    V[1] = b;
                    for(int c = 1; c < 3; c ++){
                        V[2] = c;
                        for(int d = 1; d < 3; d ++){
                            V[3] = d;
                            for(int e = 1; e < 3; e ++){
                                V[4] = e;
                                for(int f = 1; f < 3; f ++){
                                    V[5] = f;
                                    for(int ii = 0; ii < n; ii ++){
                                        for(int jj = ii; jj >= 0; jj --){
                                            if(V[jj] == V[ii] && nu[jj] == nu[ii]){
                                                C[ii] = nu[jj];
                                                break;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        if(n == 7){
            for(int a = 1; a < 3; a ++){
                V[0] = a;
                for(int b = 1; b < 3; b ++){
                    V[1] = b;
                    for(int c = 1; c < 3; c ++){
                        V[2] = c;
                        for(int d = 1; d < 3; d ++){
                            V[3] = d;
                            for(int e = 1; e < 3; e ++){
                                V[4] = e;
                                for(int f = 1; f < 3; f ++){
                                    V[5] = f;
                                    for(int g = 1; g < 3; g ++){
                                        V[6] = g;
                                        for(int ii = 0; ii < n; ii ++){
                                            for(int jj = ii; jj >= 0; jj --){
                                                if(V[jj] == V[ii] && nu[jj] == nu[ii]){
                                                    C[ii] = nu[jj];
                                                    break;
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        if(n == 8){
            for(int a = 1; a < 3; a ++){
                V[0] = a;
                for(int b = 1; b < 3; b ++){
                    V[1] = b;
                    for(int c = 1; c < 3; c ++){
                        V[2] = c;
                        for(int d = 1; d < 3; d ++){
                            V[3] = d;
                            for(int e = 1; e < 3; e ++){
                                V[4] = e;
                                for(int f = 1; f < 3; f ++){
                                    V[5] = f;
                                    for(int g = 1; g < 3; g ++){
                                        V[6] = g;
                                        for(int h = 1; h < 3; h ++){
                                            V[7] = h;
                                            for(int ii = 0; ii < n; ii ++){
                                                for(int jj = ii; jj >= 0; jj --){
                                                    if(V[jj] == V[ii] && nu[jj] == nu[ii]){
                                                        C[ii] = nu[jj];
                                                        break;
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        if(n == 9){
            for(int a = 1; a < 3; a ++){
                V[0] = a;
                for(int b = 1; b < 3; b ++){
                    V[1] = b;
                    for(int c = 1; c < 3; c ++){
                        V[2] = c;
                        for(int d = 1; d < 3; d ++){
                            V[3] = d;
                            for(int e = 1; e < 3; e ++){
                                V[4] = e;
                                for(int f = 1; f < 3; f ++){
                                    V[5] = f;
                                    for(int g = 1; g < 3; g ++){
                                        V[6] = g;
                                        for(int h = 1; h < 3; h ++){
                                            V[7] = h;
                                            for(int i = 1; i < 3; i ++){
                                                V[8] = i;
                                                for(int ii = 0; ii < n; ii ++){
                                                    for(int jj = ii; jj >= 0; jj --){
                                                        if(V[jj] == V[ii] && nu[jj] == nu[ii]){
                                                            C[ii] = nu[jj];
                                                            break;
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        if(n == 10){
            for(int a = 1; a < 3; a ++){
                V[0] = a;
                for(int b = 1; b < 3; b ++){
                    V[1] = b;
                    for(int c = 1; c < 3; c ++){
                        V[2] = c;
                        for(int d = 1; d < 3; d ++){
                            V[3] = d;
                            for(int e = 1; e < 3; e ++){
                                V[4] = e;
                                for(int f = 1; f < 3; f ++){
                                    V[5] = f;
                                    for(int g = 1; g < 3; g ++){
                                        V[6] = g;
                                        for(int h = 1; h < 3; h ++){
                                            V[7] = h;
                                            for(int i = 1; i < 3; i ++){
                                                V[8] = i;
                                                for(int j = 1; j < 3; j ++){
                                                    V[9] = j;
                                                    for(int ii = 0; ii < n; ii ++){
                                                        for(int jj = ii; jj >= 0; jj --){
                                                            if(V[jj] == V[ii] && nu[jj] == nu[ii]){
                                                                C[ii] = nu[jj];
                                                                break;
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        if(n == 11){
            for(int a = 1; a < 3; a ++){
                V[0] = a;
                for(int b = 1; b < 3; b ++){
                    V[1] = b;
                    for(int c = 1; c < 3; c ++){
                        V[2] = c;
                        for(int d = 1; d < 3; d ++){
                            V[3] = d;
                            for(int e = 1; e < 3; e ++){
                                V[4] = e;
                                for(int f = 1; f < 3; f ++){
                                    V[5] = f;
                                    for(int g = 1; g < 3; g ++){
                                        V[6] = g;
                                        for(int h = 1; h < 3; h ++){
                                            V[7] = h;
                                            for(int i = 1; i < 3; i ++){
                                                V[8] = i;
                                                for(int j = 1; j < 3; j ++){
                                                    V[9] = j;
                                                    for(int k = 1; k < 3; k ++){
                                                        V[10] = k;
                                                        for(int ii = 0; ii < n; ii ++){
                                                            for(int jj = ii; jj >= 0; jj --){
                                                                if(V[jj] == V[ii] && nu[jj] == nu[ii]){
                                                                    C[ii] = nu[jj];
                                                                    break;
                                                                }
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        if(n == 12){
            for(int a = 1; a < 3; a ++){
                V[0] = a;
                for(int b = 1; b < 3; b ++){
                    V[1] = b;
                    for(int c = 1; c < 3; c ++){
                        V[2] = c;
                        for(int d = 1; d < 3; d ++){
                            V[3] = d;
                            for(int e = 1; e < 3; e ++){
                                V[4] = e;
                                for(int f = 1; f < 3; f ++){
                                    V[5] = f;
                                    for(int g = 1; g < 3; g ++){
                                        V[6] = g;
                                        for(int h = 1; h < 3; h ++){
                                            V[7] = h;
                                            for(int i = 1; i < 3; i ++){
                                                V[8] = i;
                                                for(int j = 1; j < 3; j ++){
                                                    V[9] = j;
                                                    for(int k = 1; k < 3; k ++){
                                                        V[10] = k;
                                                        for(int l = 1; l < 3; l ++){
                                                            V[11] = l;
                                                            for(int ii = 0; ii < n; ii ++){
                                                                for(int jj = ii; jj >= 0; jj --){
                                                                    if(V[jj] == V[ii] && nu[jj] == nu[ii]){
                                                                        C[ii] = nu[jj];
                                                                        break;
                                                                    }
                                                                }
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        if(n == 13){
            for(int a = 1; a < 3; a ++){
            V[0] = a;
                for(int b = 1; b < 3; b ++){
                    V[1] = b;
                    for(int c = 1; c < 3; c ++){
                        V[2] = c;
                        for(int d = 1; d < 3; d ++){
                            V[3] = d;
                            for(int e = 1; e < 3; e ++){
                                V[4] = e;
                                for(int f = 1; f < 3; f ++){
                                    V[5] = f;
                                    for(int g = 1; g < 3; g ++){
                                        V[6] = g;
                                        for(int h = 1; h < 3; h ++){
                                            V[7] = h;
                                            for(int i = 1; i < 3; i ++){
                                                V[8] = i;
                                                for(int j = 1; j < 3; j ++){
                                                    V[9] = j;
                                                    for(int k = 1; k < 3; k ++){
                                                        V[10] = k;
                                                        for(int l = 1; l < 3; l ++){
                                                            V[11] = l;
                                                            for(int m = 1; m < 3; m ++){
                                                                V[12] = m;
                                                                for(int ii = 0; ii < n; ii ++){
                                                                    for(int jj = ii; jj >= 0; jj --){
                                                                        if(V[jj] == V[ii] && nu[jj] == nu[ii]){
                                                                            C[ii] = nu[jj];
                                                                            break;
                                                                        }
                                                                    }
                                                                }
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        if(n == 14){
            for(int a = 1; a < 3; a ++){
                V[0] = a;
                for(int b = 1; b < 3; b ++){
                    V[1] = b;
                    for(int c = 1; c < 3; c ++){
                        V[2] = c;
                        for(int d = 1; d < 3; d ++){
                            V[3] = d;
                            for(int e = 1; e < 3; e ++){
                                V[4] = e;
                                for(int f = 1; f < 3; f ++){
                                    V[5] = f;
                                    for(int g = 1; g < 3; g ++){
                                        V[6] = g;
                                        for(int h = 1; h < 3; h ++){
                                            V[7] = h;
                                            for(int i = 1; i < 3; i ++){
                                                V[8] = i;
                                                for(int j = 1; j < 3; j ++){
                                                    V[9] = j;
                                                    for(int k = 1; k < 3; k ++){
                                                        V[10] = k;
                                                        for(int l = 1; l < 3; l ++){
                                                            V[11] = l;
                                                            for(int m = 1; m < 3; m ++){
                                                                V[12] = m;
                                                                for(int o = 1; o < 3; o ++){
                                                                    V[13] = o;
                                                                    for(int ii = 0; ii < n; ii ++){
                                                                        for(int jj = ii; jj >= 0; jj --){
                                                                            if(V[jj] == V[ii] && nu[jj] == nu[ii]){
                                                                                C[ii] = nu[jj];
                                                                                break;
                                                                            }
                                                                        }
                                                                    }
                                                                }
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        if(n == 15){
            for(int a = 1; a < 3; a ++){
                V[0] = a;
                for(int b = 1; b < 3; b ++){
                    V[1] = b;
                    for(int c = 1; c < 3; c ++){
                        V[2] = c;
                        for(int d = 1; d < 3; d ++){
                            V[3] = d;
                            for(int e = 1; e < 3; e ++){
                                V[4] = e;
                                for(int f = 1; f < 3; f ++){
                                    V[5] = f;
                                    for(int g = 1; g < 3; g ++){
                                        V[6] = g;
                                        for(int h = 1; h < 3; h ++){
                                            V[7] = h;
                                            for(int i = 1; i < 3; i ++){
                                                V[8] = i;
                                                for(int j = 1; j < 3; j ++){
                                                    V[9] = j;
                                                    for(int k = 1; k < 3; k ++){
                                                        V[10] = k;
                                                        for(int l = 1; l < 3; l ++){
                                                            V[11] = l;
                                                            for(int m = 1; m < 3; m ++){
                                                                V[12] = m;
                                                                for(int o = 1; o < 3; o ++){
                                                                    V[13] = o;
                                                                    for(int p = 1; p < 3; p ++){
                                                                        V[14] = p;
                                                                        for(int ii = 0; ii < n; ii ++){
                                                                            for(int jj = ii; jj >= 0; jj --){
                                                                                if(V[jj] == V[ii] && nu[jj] == nu[ii]){
                                                                                    C[ii] = nu[jj];
                                                                                    break;
                                                                                }
                                                                            }
                                                                        }
                                                                    }
                                                                }
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        int sum = 0;
        for(int i = 0; i < n; i ++) sum += C[i];
        cout << sum;
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}
